package com.sheng.leetcode.year2023.month02.day23;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author liusheng
 * @date 2023/02/23
 * <p>
 * 1238. 循环码排列<p>
 * <p>
 * 给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：<p>
 * p[0] = start<p>
 * p[i] 和 p[i+1] 的二进制表示形式只有一位不同<p>
 * p[0] 和 p[2^n -1] 的二进制表示形式也只有一位不同<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 2, start = 3<p>
 * 输出：[3,2,0,1]<p>
 * 解释：这个排列的二进制表示是 (11,10,00,01)<p>
 * 所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]<p>
 * <p>
 * 示例 2：<p>
 * 输出：n = 3, start = 2<p>
 * 输出：[2,6,7,5,4,0,1,3]<p>
 * 解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 16<p>
 * 0 <= start < 2^n<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/circular-permutation-in-binary-representation">1238. 循环码排列</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1238 {

    @Test
    public void test01() {
        int n = 2, start = 3;
//        int n = 3, start = 2;
        System.out.println(new Solution().circularPermutation(n, start));
    }
}

class Solution {
    public List<Integer> circularPermutation(int n, int start) {
        // 取 2^n 创建一个数组，存放元素的格雷码
        int[] g = new int[1 << n];
        int j = 0;
        // 循环 0 ~ 2^n - 1
        for (int i = 0; i < 1 << n; ++i) {
            // 通过 i ^ (i >> 1) 获取到 i 的格雷码，并存放到数组 g 中
            g[i] = i ^ (i >> 1);
            // 如果 i 的格雷码等于 start
            if (g[i] == start) {
                // 使得 j = i，循环结束时，此时 j 代表最后一个能与 start 满足条件的数的坐标
                j = i;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = j; i < j + (1 << n); ++i) {
            ans.add(g[i % (1 << n)]);
        }
        return ans;
    }
}
